package simple.number;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/fizz-buzz/">412. Fizz Buzz</a>
 * 给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（下标从 1 开始）返回结果，其中：
 *   answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数。
 *   answer[i] == "Fizz" 如果 i 是 3 的倍数。
 *   answer[i] == "Buzz" 如果 i 是 5 的倍数。
 *   answer[i] == i （以字符串形式）如果上述条件全不满足。
 * 示例 1：
 *   输入：n = 3
 *   输出：["1","2","Fizz"]
 * 示例 2：
 *   输入：n = 5
 *   输出：["1","2","Fizz","4","Buzz"]
 * 示例 3：
 *   输入：n = 15
 *   输出：["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]
 * 提示：
 *   1 <= n <= 10^4
 * @author 刘学松
 * @date 2023-05-12 14:59
 */
public class FizzBuzz {
    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (isMultipleOf3(i)) {
                list.add(i%5==0?"FizzBuzz":"Fizz");
            } else if (i%5==0) {
                list.add("Buzz");
            } else {
                list.add(Integer.toString(i));
            }
        }
        return list;
    }

    public boolean isMultipleOf3(int n) {
        if (n < 0) {
            n = -n;
        }
        if (n == 0) {
            return true;
        }
        if (n == 1) {
            return false;
        }
        int oddCount = 0, evenCount=0;
        while (n > 0) {
            if ((n & 1) == 1) {
                ++oddCount;
            }
            if ((n & 2) == 2) {
                ++evenCount;
            }
            n = n >> 2;
        }
        return isMultipleOf3(oddCount-evenCount);
    }


    public boolean isMultipleOf5(int n) {
        String str = Integer.toString(n);
        char c = str.charAt(str.length() - 1);
        return c == '0' || c == '5';
    }
}
